On the spectra and symmetries of some Cayley graph-related objects
István Estélyi


Abstract

In this talk several questions in algebraic graph theory are investigated. First we will investigate the relationship between Cayley graphs, Haar graphs, Bi-Cayley graphs and vertex-transitive graphs. All these are closely related to Cayley graphs, which admit a group of automorphisms that act regularly on the set of vertices. The Haar graphs, introduced by Hladnik, Marušič and Pisanski, are bipartite graphs admitting a semiregular group of automorphisms acting regularly on each part. Haar graphs form a subclass of bi-Cayley graphs, where the two orbits do not need to be independent sets.

We will address the problem of classifying finite non-abelian groups G with the property that every Haar graph over G is a Cayley graph.  An equivalent condition for a Haar graph over G to be a Cayley graph of a group containing G is derived in terms of G, the connection set S and the automorphism group of G.

Recently Estélyi and Pisanski raised a question whether there exist vertex-transitive Haar graphs that are not Cayley graphs. We will answer this in the positive, providing an infinite family of trivalent Haar graphs that are vertex-transitive but non-Cayley. The smallest example has 40 vertices and is the well-known Kronecker cover over the dodecahedron graph, occurring as the graph `40' in the Foster census  of connected symmetric trivalent graphs.

In the last part of the talk the following group property is investigated. A finite group G is called Cayley integral if all undirected Cayley graphs over G are integral, i.e., all eigenvalues of the graphs are integers. The Cayley integral groups have been determined by Kloster and Sander in the abelian case, and by Abdollahi and Jazaeri, and independently by Ahmady, Bell and Mohar in the non-abelian case. We will generalize these results.